<?php

global $tabSommet;		// Contient un tableau dans lequel les sommets
						// sont triés par ordre alphabétique

/*************************************************************************/
function	displayAdjList($adjListTab)
{
	global $tabSommet;
	for($i = 0; $tabSommet[$i]; $i++)
	{
		echo $tabSommet[$i][0] . ": ";
		foreach($adjListTab[$tabSommet[$i][0]] as $key)
		{
			echo "$key ";
		}
		echo "\n";
	}
}
/*************************************************************************/
function	adjList($points)
{
	global $tabSommet;

	$adjListTab = array();
	for($i = 0; $tabSommet[$i]; $i++)
	{
		for ($j = 0, $count = 0; $points[$j] != NULL; $j++)
		{
			if ($tabSommet[$i][0] == $points[$j][0])
			{
				$adjListTab[$tabSommet[$i][0]][$count++] = $points[$j][1];
			}
			elseif ($tabSommet[$i][0] == $points[$j][1])
			{
				$adjListTab[$tabSommet[$i][0]][$count++] = $points[$j][0];
			}
		}
	}
	return $adjListTab;
}

/*************************************************************************/
function	checkTop($tabSommet, $top)	
{
	for ($i = 0; $tabSommet[$i][0] != NULL; $i++)
	{
		if ($tabSommet[$i][0] == $top)
			return false;
	}
	return true;
}

/*************************************************************************/

function	topCounter($points)
{
	global $tabSommet;
	$tabSommet = array();
	$tabSommet[0][0] = $points[0][0];
	$count = 1;
	for ($i = 0; $points[$i]; $i++)
	{
		for($j = 0; $points[$i][$j]; $j++)
		{
			if (checkTop($tabSommet, $points[$i][$j]))
			{
				$tabSommet[$count][0] = $points[$i][$j];
				$count++;
			}
		}
	}
	sort($tabSommet);
	echo "Nombre de sommets : $count\n";
	return $count;
}
	
/*************************************************************************/

function	 checkList($pile, $bl, $var)
{
	for ($i = 0; $i < count($bl); $i++)
		if ($bl[$i][0] == $var){
		/*	echo "bl ".$bl[$i][0]." | var ".$var."\n";*/
			return 0;
		}
	for ($c = 0; $c < count($pile); $c++)
		if ($pile[$c][0] == $var){
/*			echo "pile ".$pile[$c][0]." | var ".$var."\n";*/
			return 0;
		}
	return 1;
}
	
/*************************************************************************/
	
function	parcours($points, $start)
{
	$start[1] = 0;
	$pile = array();
	$disp = array();
	$bl = array();
	
	$disp[0][0] = $start[0];
	$disp[0][1] = $start[1];
	array_push($pile, $start);
	$wh = 0;
	while (!empty($pile))
	{
		$start = $pile[0];
		for ($i = 0; $i < count($points); $i++)
		{
			if ($points[$i][0] == $start[0] && checkList($pile, $bl, $points[$i][1]))
			{
				$end = count($disp);
				$new[0] = $points[$i][1];
				$new[1] = $start[1] + 1;
				array_push($pile, $new);
				$disp[$end][0] = $new[0];
				$disp[$end][1] = $new[1];
			}
			else if ($points[$i][1] == $start[0] && checkList($pile, $bl, $points[$i][0]))
			{
				$end = count($disp);
				$new[0] = $points[$i][0];
				$new[1] = $start[1] + 1;
				array_push($pile, $new);
				$disp[$end][0] = $new[0];
				$disp[$end][1] = $new[1];
			}
		}
		array_push($bl, $start);
		array_shift($pile);
	}
	for ($d = 0; $disp[$d]; $d++)
		echo $disp[$d][0]." ";
	echo "\n";
	for ($b = 0; $disp[$b]; $b++)
		echo $disp[$b][1]." ";
	echo "\n";
}
	
/*************************************************************************/

$file = fopen($argv[1], 'r');
echo "Fichier : ".$argv[1]."\n";
$i = -1;
$points = array();
while($line = trim(fgets($file)))
{
	if ($i < 0)
	{
		$nbArcs = $line;
		echo "Nombre d'arcs : $nbArcs\n";
	}
	else
	{
		$tmp = split(' ', $line);
		$points[$i][0] = $tmp[0];
		$points[$i][1] = $tmp[1];
	}
	$i++;
}
$top = topCounter($points);
displayAdjList(adjList($points));
$start = $tabSommet[rand() % count($tabSommet)][0];
echo "Parcours en largeur a partir du sommet ".$start."\n";
parcours($points, $start);
?>
